One of path search techniques performed with path controllers such as a router and a layer 3 switch is a tree method. In the tree method, destination address information, such as MAC addresses and IP addresses, is arranged in a tree structure. At the time of a path search, a path controller follows node points (hereinafter called “nodes”) according to a search key (address information) and acquires path information when reaching an external node (hereinafter called a “leaf”). FIG. 10 shows an example of a tree structure when the path controller has path information for 7-bit destination address information shown in Table 1.
TABLE 1DESTINATION ADDRESS INFORMATION0010100010001001100001000010100001110001111010000101000111000101110110
The tree of FIG. 10 assumes the form of a Patricia tree. The numerical value within each node N indicates the number of high-order bits that are common to every piece of destination address information registered with leaves L belonging to the node N. For example, when considering a node N3, destination address information within the leaves L belonging to the node N3 includes “1000010,” “1000011,” and “1000111,” and the high-order 4 bits, “1000,” of the three pieces of destination address information are common. Therefore, the numerical value within the node N3 is set to “4.”
The edge (branch) is divided into two from the node N3, depending on whether the numerical value of the fifth high-order bit of the destination address information within the leaves L belonging to the node N3 is “0” or “1.” Among the above-mentioned three pieces of destination address information, the fifth high-order bit of “1000010” and “1000011” is “0,” indicating that the leaves L including these destination address information belong to the edge of “0.” On the other hand, since the fifth high-order bit of “1000111” is “1,” the leaf L having this destination address information belongs to the edge of “1.”
When receiving a frame having destination address information “1000010” from the outside, a conventional path controller extracts the destination address information“1000010” from the received frame. The path controller then performs a path search in the Patricia tree shown in FIG. 10 by using the extracted destination address information as a search key. In FIG. 10, the path search starts at a root R. Since the first high-order bit of the search key is “1,” it goes to the edge of “1” from the root R, and reaches a node N1. The numerical value within the node N1 is “1” (namely, the first high-order bit of all the destination address information on the leaves L belonging to the node N1 is “1”), so that either of the edges “0” and “1” emanating from the node N1 is determined by the numerical value of the second high-order bit. Then, since the second high-order bit of the search key (“1000010”) is “0,” it goes to the edge of “0” and reaches a node N2. The numerical value within the node N2 is “2,” so that, based on the numerical value “0” of the third high-order bit of the search key, it goes the edge of “0” and reaches a node N3. It teaches a node N4 in the same manner, and a leaf L1 is finally searched for. In addition to the destination address information, path information indicating the location where a frame haying the destination address information should go is registered in each leaf L. The path controller acquires the path information within the leaf L1, and transfers the received frame based on the path information.
Thus, in the search method for the conventional path controller, the plurality of nodes N1 to N4 need to be passed through during the search. Since the more the number of passing nodes N the longer the search time, it is preferable that the number of passing nodes is small.
Japanese Patent Laid-Open No. 2001-357071 proposes path search using a tree structure. In the patent document, the path search is performed using a tree structure having a “direct table.” FIG. 11 shows the tree structure based on the patent document for the plurality of leaves L including the destination address information on the table 1. Referring to FIG. 11, the tree structure having the direct table includes a direct table DT instead of the root R in FIG. 10. In the direct table DT, eight combinations of high-order 3 bits of destination address information are registered (hereinafter, the combinations are called the DT entries 0 to 7). When two or more leaves L belong to the same DT entry, a node(s) N is provided in the same manner as in the conventional method. In FIG. 11, since three leaves L (destination address information=“1000010,” “1000011,” “1000111”) belong to the DT entry 4 (with high-order 3 bits of “100”), the DT entry 4 has nodes N3 and N4 in the same manner as in FIG. 10. Providing the direct table DT can reduce the number of nodes N (hereafter called the number of node-stages) which must be passed through before reaching the leaves L during the path search. For example, it is necessary to pass through four nodes N1 to N4 in the tree structure of FIG. 10 before reaching the leaf L1 having the destination address information “1000010” during the path search. In contrast, in the tree structure of FIG. 11, since there is the direct table DT, only the two nodes N3 and N4 need to be passed through after starting from the DT entry 4 until reaching the target leaf L1. Thus, the tree structure having the direct table DT can reduce the number of node-stages, thereby reducing the search time.
However, even in the tree structure having the direct table DT, the number of node-stages N can vary depending on the destination address information included in a plurality of leaves L. FIG. 12 shows a tree structure having the direct table DT when eight leaves L belong to one DT entry. In FIG. 12A, the number of leaves L belonging to nodes N10 and N11 is four, respectively, showing a case where the leaves L are uniformly distributed. In this case, the number of node-stages passed through before reaching a leaf L2 in this figure is two. On the other hand, FIG. 12B shows a tree structure when leaves L are distributed in the most nonuniform manner possible. In FIG. 12B, the number of node-stages for reaching the leaf L2 is seven. Therefore, even in the tree structure having the direct table DT, when a deviation of leaves occurs in the tree structure, the number of node-stages increases to increase the path search time.